package mycollections;

import java.util.Iterator;
import java.util.NoSuchElementException;


public class MyLinkedList<T> implements MyList<T>, MyQueue<T>, MyStack<T> {

	Node<T> first;
	Node<T> last;
	int size;
	
	public MyLinkedList() {		
	}

	public MyLinkedList(MyList<T> c)  {
		addAll(size, c.toArray());
	}
	
	public void add(T e) {
		linkLast(e);
	}
	
	public void push(T e) {
		addFirst(e);
	}
	
	public T pop() {
		return removeFirst();
	}
	
	public void offer(T e) {
		linkLast(e);
	}	
	
	public T peek() {
		if(first == null)
			return null;
		return getFirst();
	}
	
	public T poll() {	
		if(first == null)
			return null;
		return removeFirst();
	}
	
	public void addFirst(T e) {
		if(first == null) {
			first = new Node<T>(e);
			last = first;
			size++;
		}
		else linkBefore(e, first);
	}
	
	public void addLast(T e) {
		linkLast(e);
	}
	
	public T getFirst() {
		if(first == null)
			throw new NoSuchElementException();
		return first.value;
	}
	
	public T getLast() {
		if(last == null)
			throw new NoSuchElementException();
		return last.value;
	}
	
	public T removeFirst() {		
		if(first == null)
			throw new NoSuchElementException();		
		return unlink(first);		
	}
	
	public T removeLast() {		
		if(last == null)
			throw new NoSuchElementException();
		return unlink(last);
	}

	public void add(int index, T e) {
		checkIndex(index);
		if (index == size)
			linkLast(e);
		else
			linkBefore(e, getNode(index));
	}
	
	public void addAll(T[] c) {
		addAll(size, c);
	}
	
	public void addAll(int index, Object[] c) {
		checkIndex(index);
		Node<T> succ, pred;
		if (index == size) {
			succ = null;
			pred = last;
		} else {
			succ = getNode(index);
			pred = succ.prev;
		}
		for (Object cur : c) {
			@SuppressWarnings("unchecked") T t = (T) cur;
			Node<T> newNode = new Node<T>(pred, t, null);
			if (pred == null)
				first = newNode;
			else
				pred.next = newNode;
			pred = newNode;
			size++;
		}
		if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }        
	}
	
	public T get(int index) {
		checkIndex(index);
		return getNode(index).value;
	}
	
	public T remove(int index) {
		checkIndex(index);
		return unlink(getNode(index));
	}	
	
	public void clear() {
		for(Node<T> cur = first; cur != null; ) {
			Node<T> next = cur.next;
			cur.prev = null;
			cur.next = null;
			cur.value = null;
			cur = next;
		}
		first = last = null;
		size = 0;
	}
	
	public boolean isEmpty() {
		return size == 0;
	}
	
	public void set(int index, T e) {
		checkIndex(index);
		getNode(index).value = e;
	}
	
	public int indexOf(T e) {
		int index = 0;
		if (e == null) {
            for (Node<T> nextNode = first; nextNode != null; nextNode = nextNode.next) {
                if (nextNode.value == null)
                    return index;
                index++;
            }
        } else {
			for(Node<T> nextNode = first; nextNode != null; nextNode = nextNode.next) {
				if(e.equals(nextNode.value))
					return index;
				index++;
			}
        }
		return -1;
	}
	
	public int size() {
		return size;
	}
	
	public Object[] toArray() {
		Object[] result = new Object[size];
		int i = 0;
		for(Node<T> nextNode = first; nextNode != null; nextNode = nextNode.next)
			result[i++] = nextNode.value;		
		return result;
	}
	
	public Iterator<T> iterator() {
		return new MyLinkedListIterator();
	}
	
	public Iterator<T> descendingIterator() {
		return new MyLinkedListDescendingIterator();
	}
	
	private void checkIndex(int index) {
		if(index < 0 || index > size)			
			throw new MyIndexOutOfBoundsException("Index: "+index+", Size: "+size);		
	}
	
	private T unlink(Node<T> nodeToRemove) {
		T value = nodeToRemove.value;
		Node<T> prev = nodeToRemove.prev;
		Node<T> next = nodeToRemove.next;
		if(prev == null) 
			first = next;
		else {
			prev.next = next;
			nodeToRemove.prev = null;
		}
		if(next == null)
			last = prev;
		else {
			next.prev = prev;
			nodeToRemove.next = null;
		}		
		nodeToRemove.value = null;
		size--;
		return value;
	}

	private void linkLast(T e) {
		Node<T> newNode = new Node<T>(e);
		if (first == null) {
			first = last = newNode;
		} else {
			last.next = newNode;
			newNode.prev = last;
			last = newNode;			
		}
		size++;
	}

	private void linkBefore(T e, Node<T> succ) {			
		Node<T> pred = succ.prev;
		Node<T> newNode = new Node<T>(pred, e, succ);
		succ.prev = newNode;
		if (pred == null)
			first = newNode;
		else
			pred.next = newNode;
		size++;
	}

	private Node<T> getNode(int index) {
		if (index < size / 2) {
			Node<T> cur = first;
			for (int i = 0; i < index; i++)
				cur = cur.next;
			return cur;
		} else {
			Node<T> cur = last;
			for (int i = size - 1; i > index; i--)
				cur = cur.prev;
			return cur;
		}
	}
	
	private class MyLinkedListIterator implements Iterator<T> {
		
		private Node<T> next;
		private Node<T> lastRet;
		private int nextIndex;

		public MyLinkedListIterator() {
			if(size == 0)
				next = null;
			else next = getNode(0);
			nextIndex = 0;
		}
		
		public boolean hasNext() {			
			return nextIndex < size();
		}

		public T next() {			
			if (!hasNext())
                throw new NoSuchElementException();
			lastRet = next;
			next = next.next;
			nextIndex++;
			return lastRet.value;
		}

		public void remove() {
			if (lastRet == null)
                throw new IllegalStateException();
			Node<T> lastNext = lastRet.next;
			unlink(lastRet);
			nextIndex--;
			next = lastNext;
			lastRet = null;				
		}
		
	}
	
private class MyLinkedListDescendingIterator implements Iterator<T> {
		
		private Node<T> next;
		private Node<T> lastRet;
		private int nextIndex;

		public MyLinkedListDescendingIterator() {
			if(size == 0)
				next = null;
			else next = getNode(size-1);
			nextIndex = 0;
		}
		
		public boolean hasNext() {
			return nextIndex < size;
		}

		public T next() {
			if (!hasNext())
                throw new NoSuchElementException();
			lastRet = next;
			next = next.prev;
			nextIndex++;
			return lastRet.value;
		}

		public void remove() {
			if (lastRet == null)
                throw new IllegalStateException();
			Node<T> lastNext = lastRet.prev;
			unlink(lastRet);
			nextIndex--;
			next = lastNext;
			lastRet = null;				
		}
		
	}

	static class Node<T> {

		Node<T> next;
		Node<T> prev;
		T value;

		public Node(T value) {
			this.value = value;
		}

		public Node(Node<T> pred, T e, Node<T> succ) {
			this.prev = pred;
			this.value = e;
			this.next = succ;
		}

	}

}
